1. Field of the Invention
The present invention relates to data networking and in particular to controlling packet flooding on VLANs contained in a data network.
2. Background Information
A data network is a geographically distributed collection of interconnected communication links and segments for transporting data between nodes, such as computers. The nodes typically transport the data over the network by exchanging discrete frames or packets containing the data in accordance with various pre-defined protocols, such as e.g., the Transmission Control Protocol/Internet Protocol (TCP/IP) or the Institute of Electrical and Electronics Engineers (IEEE) 802.3 protocol. In this context, a protocol consists of a set of rules defining how the nodes interact with each other to transfer data between them.
Many types of networks are available, with types ranging from local area net-works (LANs) to wide area networks (WANs). LANs typically connect nodes, such as personal computers and workstations, over dedicated private communication links located in the same general physical location, such as a building or a campus, to form a private network. WANs, on the other hand, typically connect large numbers of geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines. The Internet is an example of a WAN that connects disparate net-works throughout the world, providing global communication between nodes contained in various networks. WANs often comprise a complex network of intermediate network nodes, such as routers or switches, that are interconnected to form the WAN and are often configured to perform various functions associated with transferring traffic through the WAN.
Some organizations implement virtual LANs (VLANs) in their private networks to “logically” group entities, such as users, servers, and other resources within the organization. A VLAN is a logical group of entities, such as end nodes and servers, which appear to one another as if they are on the same physical LAN segment even though they may be spread across a large network comprising many different physical segments. A VLAN operates at the data link layer, which is layer-2 (L2) of the Open Systems Interconnect (OSI) reference model.
An organization may utilize one or more intermediate nodes, such as L2 switches, to couple various entities in the network that belong to a particular VLAN. These intermediate nodes may employ special hardware or software that is configured to “learn” various information about the entities belonging to the VLAN and place this information in a forwarding database that is used by the intermediate node to forward packets acquired by the node to the various entities. The learned information may include a VLAN and a media access control (MAC) address associated with the entity, as well as a port identifier (ID) of a port on the intermediate node through which the entity may be reached.
Often intermediate nodes employ a content-addressable memory (CAM) to store the forwarding database information. CAMs are usually implemented in hardware as an application specific memory device that allows its entire contents to be searched within a single clock cycle. Two common types of CAMs include binary CAMs and ternary CAMs (TCAMs). A binary CAM performs exact-match searches, whereas a TCAM allows pattern matching with the use of “don't cares” which act as wildcards during a search. Because TCAMs are somewhat more versatile than binary CAMs, intermediate nodes often employ one or more TCAM devices to implement the intermediate node's forwarding database.
TCAM devices are often limited with regards to their storage capacity. For example, a typical TCAM device may contain upwards to 32,768 (32K) entries. In a typical forwarding database arrangement, the TCAMs are configured such that each entry holds forwarding database information associated with a particular entity accessible to the intermediate node. Thus, forwarding databases implemented using TCAM devices are often limited to containing information for only up to 32K entities.
The entries in a forwarding database are typically populated using a technique known as “learning.” Learning involves identifying information about an entity in the network, such as a MAC address, VLAN, and destination port associated with the entity, and placing this information in a forwarding database entry. For example, assume an intermediate node acquires a packet on a source port “C” containing a source MAC address “A.” Further assume the port is associated with a VLAN “B.” The intermediate node applies the MAC address “A” to its forwarding database to determine if an entry associated with entity “A” already exists in the database. Assuming an entry does not exist, the intermediate node “learns” about the entity by placing the entity's address, VLAN and source port information associated with the entity in an entry in its forwarding database. Thus, in the above example, the intermediate node creates an entry in the forwarding database associated with the entity that contains “A,” “B” and “C” to represent the address, VLAN and source port associated with the entity, respectively. The intermediate node may later use this information to forward packets that are destined for the entity.
In addition to learning, an intermediate node may further process a packet by performing a “lookup” operation to identify a destination port associated with the packet and forwarding the packet to the destination port. The lookup operation may involve applying a destination address contained in the packet to the forwarding database to determine if the database contains an entry with an address that matches the destination address. If a matching entry is found, the intermediate node forwards the packet to the destination node via a destination port specified in the matching entry. If a matching entry is not found, the intermediate node may alternatively “flood” the packet out all ports in an attempt to reach the destination node. Flooding usually involves sending a copy of the packet onto each of the intermediate node's ports, except the source port on which the packet was acquired.
One problem with the learning technique described above is that it is possible for entities belonging to a VLAN to occupy all or an inordinate amount of the entries in a forwarding database, thus potentially causing the intermediate node to constantly learn about entities belonging to other VLANs. For example, if the number of entities belonging to a particular VLAN is greater than the number of entries in a forwarding table, it is possible for the forwarding table to contain only entries associated with that VLAN. Entries associated with entities from other VLANs end up being displaced and, consequently, have to be re-learned. This could lead to a continuous cycle of displacement and re-learning that, in turn, may significantly impact the packet processing performance of the intermediate node.
Another problem that may occur when a VLAN's entities occupy all or an inordinate amount of entries in a forwarding table is excessive flooding, particularly when processing packets destined for entities belonging to other VLANs. Such excessive flooding may cause the network's performance to be degraded significantly. For example, assume, as above, a first VLAN has more entities than entries in a forwarding database and that the entities are active and that the entire database is occupied with entries associated with the entities. Packets acquired from a second VLAN would have to be flooded because the forwarding database would not contain an entry associated with the destination addresses of the acquired packets. If the first VLAN continually occupies all the entries in the forwarding database before packets from the second VLAN are acquired and processed, the packets for the second VLAN would have to be continually flooded which, in turn, may lead to excessive traffic being generated and introduced into the network when processing packets for the second VLAN. This excessive traffic may further lead to network congestion and consequently network degradation.